package LimitedTimeGame.Day_0222;

/**
 * @author zxc
 * @date 2023/02/22 10:23
 **/

import java.util.Arrays;

/**
 * 题目 ：石子游戏二
 * 题目详述 ：
 * 给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
 * 每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:
 * 0 <= j <= nums[i]
 * i + j < n
 * 返回到达nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。
 *
 * 提示:
 * 1 <= nums.length <= 104
 * 0 <= nums[i] <= 1000
 * 题目保证可以到达 nums[n-1]
 *
 */
public class Jump02 {
    public static void main(String[] args) {
        System.out.println(jump(new int[]{3,4,3,2,5,4,3}));
    }
    /**
     * 思路 ：
     * 动态规划
     * ===》
     * 假设f(i)是 跳跃到达第i个位置所需要的最小步数;
     * 状态转移方程 ：
     * f(i) = min(f(i - k) + 1);
     * 其中，k为所有能够到达 第i个位置的元素;
     *
     * @param nums
     * @return
     */
    public static int jump(int[] nums) {
        int len = nums.length;
        int[] dp = new int[len];
        Arrays.fill(dp , len + 1);
        dp[0] = 0;
        // 即，遍历每一个位置 开始跳跃到 其能够到达位置的所有情况 && 跳跃到每个位置所需要的最少步数
        for(int i = 0 ; i < len ; i++){
            for(int j = 1 ; i + j < len && j <= nums[i] ; j++){
//                 即，能够跳跃到nums数组尾部元素;
                if(i + j >= len){
                    /**
                     * 思考 ：
                     * 为什么dp[len - 1]中一出现可能到达的跳跃次数，就可以直接返回
                     * ===》
                     * 由于辅助数组dp中，所记录的元素必然为 11...2...3..n...等等;
                     * 即，记录了第一次跳跃所能够到达的所有数组下标...第n次跳跃所能够到达的所有数组下标;
                     * 辅助数组dp中的元素是连续的，并不是离散的;
                     */
                    return dp[len - 1];
                }
                // 使得dp[i + j]保存的是到达该位置的最少跳跃次数
                // （按道理来说，由于是迭代遍历，所以第一次记录下到达该位置的跳跃次数就是 最少跳跃次数）
                // 取最小值，即是为了防止后续 能够到达该位置的跳跃次数 覆盖掉最少跳跃次数;
                dp[i + j] = Math.min(dp[i + j] , dp[i] + 1);
            }
        }
        return dp[len - 1];
    }
}